/* 
 * Copyright (C) 2013, 2014 lex xiang
 *
 * file:	sys/rbtree.h
 * history:	2013 Juy 25 created by lex
 */

#ifndef __RBTREE_H__
#define __RBTREE_H__

#include "types.h"
#include "list.h"

#define RB_RED		0
#define RB_BLACK	1

struct rb_node {
	struct rb_node	*parent;

	unsigned int	color;

	struct rb_node	*left_child;
	struct rb_node	*right_child;
};

#define rb_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

struct rb_tree;
typedef struct rb_node **(*fp_rbtree_find)(struct rb_tree *, struct rb_node *, void *);
typedef void (*fp_rbtree_insert)(struct rb_tree *, struct rb_node *, 
				 struct rb_node*, struct rb_node **);
typedef void (*fp_rbtree_erase)(struct rb_tree *, struct rb_node *);
typedef s32 (*fp_rbtree_cmp)(struct rb_node *, void *);

struct rb_tree {
	struct rb_node *root;
	struct rb_node *first;

	struct {
		fp_rbtree_find		find;
		fp_rbtree_insert	insert;
		fp_rbtree_erase		erase;
		fp_rbtree_cmp		cmp;
	} op;
};

#define INIT_RB_NODE()	{NULL, RB_RED, NULL, NULL}
#define INIT_RB_TREE()	{NULL, NULL, {NULL, NULL, NULL}}

extern void rb_tree_init(struct rb_tree *, fp_rbtree_find,
			 fp_rbtree_insert, fp_rbtree_erase, fp_rbtree_cmp);
extern struct rb_node **rb_find(struct rb_tree *, struct rb_node *, void *);
extern void rb_insert(struct rb_tree *, struct rb_node *, 
		      struct rb_node *, struct rb_node **);
extern void rb_erase(struct rb_tree *, struct rb_node *);
extern struct rb_node *rb_next(struct rb_node *node);
extern struct rb_node *rb_prev(struct rb_node *node);

#endif	/* end of __RBTREE_H__ */
